<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-19 21:05:07
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-19 21:26:50
-->
<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-19 21:05:07
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-19 21:06:21
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树的所有路径</title>
</head>

<body>
    <script>
        // 给定一个二叉树，返回所有从根节点到叶子节点的路径。
        // 说明: 叶子节点是指没有子节点的节点。
        // 这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

        //     在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一一个路径在进入另一个路径。

        //     前序遍历以及回溯的过程如图：

        // 递归法
        /**
         * @name: binaryTreePath
         * @msg: 函数注释
         * @param {root} root:根结点
         * @return {res}res:返回值
         */
        var binaryTreePath = function (root) {
            let res = [];
            /**
             * @name: getPath
             * @msg: 获取路径
             * @param {*} node节点
             * @param {*} path路径
             * @return {*} '';
             */
            const getPath = function (node, path) {
                if (node.left == null && node.right == null) {
                    path += node.val;
                    res.push(path);
                    return '';
                }
                path += node.val + '->';
                node.left && getPath(node.left, path);
                node.right && getPath(node.right, path);

            }

            getPath(root, '');
            return res;
        }

        // 迭代法
        /**
         * @name: binaryTreePath
         * @msg: 迭代法寻找二叉树路径
         * @param {*} root：二叉树
         * @return {*}返回路径
         */
        var binaryTreePath = function (root) {
            if (!root) {
                return [];
            }
            const stack = [root], path = [''], res = [];
            while (stack.length) {
                const node = stack.pop();
                let path = path.pop();
                if (!node.left && !node.right) {
                    res.push(path + node.val);
                    continue;
                }
                path += node.val + '->';
                if (node.right) {
                    stack.push(node.right);
                    path.push(path);
                }
                if (node.left) {
                    stack.push(node.left);
                    path.push(path);
                }
            }
            return res;

        }


    </script>

</body>

</html>